package domain.simplex;

import utils.exception.SimplexException;
import utils.exception.SimplexInfeasibleException;

public class Simplex {

	// algorithm: Cormen Algorithm P795
	public static SimplexSlackForm pivoting(SimplexSlackForm sf, int l, int e) {
		// compute the coefficient of the equation for new basic var x_e
		double newb_e = sf.getBi(l) / sf.getAij(l, e);
		sf.setBi(e, newb_e);
		// leaving var's Bi should now be 0, as it is nonbasic now.
		sf.setBi(l, 0);
		// remove them
		sf.rmNonBasicVar(e);
		sf.rmBasicVar(l);
		// update coefficients for new basic var e
		for (Integer j : sf.getNonbasicVars()) {
			if (j == e) {
				continue;// should not enter
			}
			double newa_ej = sf.getAij(l, j) / sf.getAij(l, e);
			sf.setAij(e, j, newa_ej);
		}
		double newa_el = 1.0 / sf.getAij(l, e);
		sf.setAij(e, l, newa_el);
		// compute coefficients for other basic vars
		for (Integer i : sf.getBasicVars()) {
			if (i == l) {
				continue; // should not enter
			}
			double newb_i = sf.getBi(i) - sf.getAij(i, e) * newb_e;
			sf.setBi(i, newb_i);
			for (Integer j : sf.getNonbasicVars()) {
				if (j == e) {
					continue;// should not enter
				}
				// if(j == 4){
				// System.out.println("newa_ij");
				// }
				double newa_ij = -1.0 * sf.getAij(i, e) * sf.getAij(e, j)
						+ sf.getAij(i, j);

				sf.setAij(i, j, newa_ij);
			}
			// finish by adding the last one a_il
			double newa_il = -1.0 * (sf.getAij(i, e) * newa_el);
			sf.setAij(i, l, newa_il);
			// set entering var's coefficient: a_i_e =0
			sf.setAij(i, e, 0);
		}

		// compute the objective function
		double newv = sf.getV() + sf.getCj(e) * newb_e;
		sf.setV(newv);
		for (Integer j : sf.getNonbasicVars()) {
			if (j == e) {
				continue;// should not enter
			}
			double newc_j = sf.getCj(j) - sf.getCj(e) * sf.getAij(e, j);
			sf.setCj(j, newc_j);
		}
		// update c_l
		double newc_l = -1 * (sf.getCj(e) * newa_el);
		sf.setCj(l, newc_l);
		// update entering var's Cj value, -->0
		sf.setCj(e, 0);
		// add new basic/nonbasic vars
		sf.addAsNonBasicVar(l);
		sf.addAsBasicVar(e);
		sf.clearAijRow(l);
		return sf;
	}

	// the simplex method
	// sf: should have no Nonbasic vars, basic vars, nor v
	public static void findSolution(SimplexSlackForm sf)
			throws SimplexException, SimplexInfeasibleException {
		SimplexSlackForm isf = new SimplexInitializer(sf).initialize();
		int e = findPosNBVar(isf);
		while (e >= 0) {
			int result = theWhileLoop(isf, e);
			if (result < 0) {
				throw new SimplexException("Unbounded. Quit.");
			}
			e = findPosNBVar(isf);
		}
		// finalize, display the solution, assume that x_1->x_n are the original
		// vars
		for (int i = 0; i < sf.getBasicVars().size(); i++) {
			int var = sf.getBasicVars().get(i);
			System.out.println("X_" + var + " = " + sf.getBi(var));
		}
		for (int i = 0; i < sf.getNonbasicVars().size(); i++) {
			int var = sf.getNonbasicVars().get(i);
			System.out.println("X_" + var + " = " + 0);
		}
	}

	// return 0+ if found, -1 otherwise
	public static int findPosNBVar(SimplexSlackForm isf) {
		// find a positive nonbasic var to loop
		for (int j = 0; j < isf.getCj().length; j++) {
			if (isf.getCj(j) > 0) {
				// return isf.getNonbasicVars(j);
				return j;
			}
		}
		return -1;
	}

	// c[e]>0, still valid to loop
	// return: -1 if unbounded, otherwise 0
	public static int theWhileLoop(SimplexSlackForm isf, int e) {
		double[] slacks = new double[isf.numOfAllVars() + 1];
		for (Integer i : isf.getBasicVars()) {
			double coefficient = isf.getAij(i, e);
			if (coefficient > 0) {
				slacks[i] = isf.getBi(i) / coefficient;
			} else {
				// this entry i is unbound
				slacks[i] = Double.MAX_VALUE;
			}
		}
		// choose the minimum slack
		int l = minIndex(slacks);
		if (slacks[l] == Double.MAX_VALUE) {
			return -1;
		} else {
			pivoting(isf, l, e);
		}
		return 0;
	}

	private static int minIndex(double[] slacks) {
		int ret = 0;
		// avoid the zeros
		for (int i = 0; i < slacks.length; i++) {
			if (slacks[i] == 0) {
				continue;
			}
			if (slacks[ret] == 0) {
				ret = i;
			}
			if (slacks[i] < slacks[ret]) {
				ret = i;
			}
		}
		return ret;
	}

}
